The present invention relates to a method for generating a block-based image histogram from data compressed by JPEG, MPEG-1, and MPEG-2, or uncompressed image data. In particular, the method employs block-based linear quantization to generate histograms that include color, brightness, and edge components.
JPEG is the international standard for still images and MPEG-1, 2 are for moving pictures. Regarding the compressed image information, feature information is necessary for applications such as extracting key frames, searching images, and browsing.
To extract such feature information, a brightness and color histogram that express relative frequency of brightness and color (red, green, blue) in an image is widely used. Methods comparing histograms have been proposed for searching digital video applications. As histograms are used for searching images and detecting motion change, it is proposed that conventional histograms be improved. That is, conventional single component histograms with discrete quantization and color have been developed, and therefore composite histograms that employs linear update and soft decision are adopted for effective and efficient image description.
U.S. Pat. No. 5,805,733 xe2x80x9cMethod and system for detecting scenes and summarizing video sequencexe2x80x9d disclosed a method that employs color histograms and edge maps for detecting motion change. Though the method is effective in that it extracts color information in consideration of the human eye, it doesn""t use brightness information. A method disclosed by a technical paper xe2x80x9cColor Indexingxe2x80x9d published by International Journal of Computer Vision receives color information and measures similarity of images by histogram intersection method. However, this method doesn""t use brightness information and therefore accuracy is not good enough. Also, since the conventional methods generate histograms using a discrete quantization method, a relatively large number of histogram bins are needed to achieve good performance. Consequentially, these methods are not efficient in terms of storage and similarity measurement.
In addition, because the conventional methods perform feature extraction in terms of pixel in generating histograms, feature information is very restrictively generated.
A method for generating a block-based image histogram is provided.
A method for generating a block-based image histogram using a color information and a brightness information of an image data includes the following steps. The first step is to extract edge information of an image in terms of a block. The second step is to update edge histogram bins on the basis of the edge information to generate a global edge histogram.
Preferably, the step of extracting the edge information further comprises the following steps. The first step is to divide the block into a plurality of sub-blocks by dividing the block by half with respect to horizontal direction and dividing the block by half with respect to vertical direction. The second step is to obtain brightness representative values of the sub-blocks, respectively. The third step is to determine if an edge exists in the block and determining an edge type by comparing a brightness difference between the adjacent sub-blocks with a threshold.
Preferably, the determining step determines that the edge exists and detects the edge type if the brightness difference is larger than the threshold or determines that the block is a monotone block if the brightness difference is not larger than the threshold.
Preferably, the brightness representative value of the sub-block is an average value of the pixels within the sub-block.
Preferably, the brightness representative value of the sub-block is a median value of the pixels within the sub-block.
Preferably, another method of extracting the edge information comprises the following steps. The first step is to divide the block into four sub-blocks by dividing the block by half with respect to a horizontal direction and dividing the block by half with respect to a vertical direction. The second step is to obtain brightness representative values of the sub-blocks, respectively. The third step is to obtain an edge value of 0 degree, an edge value of 45 degree, an edge value of 90 degree, an edge value of 135 degree, and a complex edge value by convoluting the brightness representative values with filter coefficients. The fourth step is to determine if an edge exists in the block and determining an edge type by comparing a maximum edge value with a threshold, wherein the maximum edge value is the largest value among the edge value of 0 degrees, the edge value of 45 degrees, the edge value of 90 degrees, the edge value of 135 degrees, and a complex edge value.
Preferably, the obtaining step of the edge value of 0 degrees, the edge value of 45 degrees, the edge value of 90 degrees, the edge value of 135 degrees, and the complex edge value is calculated by applying the brightness representative values and the filter coefficients to following equations.       edge90    =          "LeftBracketingBar"                        ∑                      i            =            0                    3                ⁢                  (                      mean_sub            ⁢            _block            ⁢                          (              i              )                        xc3x97            edge90_filter            ⁢                          xe2x80x83                        ⁢                          (              i              )                                )                    "RightBracketingBar"            edge0    =          "LeftBracketingBar"                        ∑                      i            =            0                    3                ⁢                  (                      mean_sub            ⁢            _block            ⁢                          (              i              )                        xc3x97            edge0_filter            ⁢                          xe2x80x83                        ⁢                          (              i              )                                )                    "RightBracketingBar"            edge45    =          "LeftBracketingBar"                        ∑                      i            =            0                    3                ⁢                  (                      mean_sub            ⁢            _block            ⁢                          (              i              )                        xc3x97            edge45_filter            ⁢                          xe2x80x83                        ⁢                          (              i              )                                )                    "RightBracketingBar"            edge135    =          "LeftBracketingBar"                        ∑                      i            =            0                    3                ⁢                  (                      mean_sub            ⁢            _block            ⁢                          (              i              )                        xc3x97            edge135_filter            ⁢                          xe2x80x83                        ⁢                          (              i              )                                )                    "RightBracketingBar"            complex_edge    =          "LeftBracketingBar"                        ∑                      i            =            0                    3                ⁢                  (                      mean_sub            ⁢            _block            ⁢                          (              i              )                        xc3x97            complex_edge            ⁢            _filter            ⁢                          xe2x80x83                        ⁢                          (              i              )                                )                    "RightBracketingBar"      
wherein the edge90_filter(i), the edge45_filter(i), the edge135_filter(i), and the complex_edge_filter(i) are filter coefficients, and wherein the mean_sub_block(i) is average brightness value of ith sub-block.
Preferably, the method for generating a block-based image histogram in accordance with an embodiment of the present invention further comprises the following step of grouping the blocks and thereby generating a local edge histogram using the edge information extracted from each block in terms of the local regions.
Preferably, the method for generating a block-based image histogram in accordance with an embodiment of the present invention further comprises the following step of grouping the local regions with respect to horizontal direction and vertical direction and thereby generating a semi-global edge histogram using the edge information extracted from each block in terms of the semi-global regions.
Preferably, the global histogram, semi-global histogram, and the local histogram are normalized separately.
Preferably, the method for generating a block-based image histogram in accordance with an embodiment of the present invention further comprises the following steps. The first step is to initialize a variable k and determining a block size of level k by grouping the pixels of the image. The second step is to update related histogram bins by extracting a feature information of the image in terms of a block regarding all blocks of the level k. The Third step is to update related histogram bins by grouping blocks of level k to form a block of level k+1, merge the feature information of the level k, and extract the feature information of the image in terms of a block regarding all blocks of the level k+1.
Preferably, the method for generating a block-based image histogram using color information and brightness information of image data comprises the following steps. The first step is to extract the color information and the brightness information by employing a linear weight depending on a distance between histogram bins. The second step is to update values of the histogram bins to minimize a quantization error occurring at a boundary between the histogram bins.
Preferably, the step of extracting the color information and the brightness information further comprise the following steps. The first step is to express a hue and a saturation of the color from the given color space. The second step is to obtain the linear weight between the saturated representative colors and the linear weight between unsaturated color and saturated color using the hue and the saturation of the color. The third step is to determine if the color of the block is a pure color or a dark saturated color usint the saturation. The fourth step is to calculate an increase of color histogram bins with the linear weight and updating related color histograms if color of the block is pure color or calculating an increase of color histogram bins and brightness histogram bins with the linear weight and linear weight and updating related color histograms and related brightness histograms if the color of the block is a dark saturated color.
Preferably, if the color space is YCbCr color space, from the Cb, Cr components, hue and saturation values are obtained by equation 1 and equation 2, respectively.                     ph        =                              tan                          -              1                                ⁢                      Cb            Cr                                              [                  Equation          ⁢                      xe2x80x83                    ⁢          1                ]                                ps        =                                            Cr              2                        +                          Cb              2                                                          [                  Equation          ⁢                      xe2x80x83                    ⁢          2                ]            
Preferably, the sum of increases of color histogram bins in terms of a block normalizes to 1.
A method for generating a block-based image Histogram using color information and brightness information of image data in accordance with an embodiment of the present invention includes following steps. The first step is to group a plurality of pixels of the image into a block. The second step is to divide the block into four sub-blocks by dividing the block by half with respect to a horizontal direction and dividing the block by half with respect to a vertical direction and then obtaining brightness representative values of the sub-blocks and determining if an edge exists in the block and an edge type by comparing a brightness difference between the adjacent sub-blocks with a threshold. The third step is to increase related edge histogram bins on the basis of the edge type and thereby updating the edge histograms. The fourth step is to obtain a hue and a saturation of the color from a color space of the image and to obtain a linear weight between representative saturated colors and a linear weight between the saturated color and a unsaturated color. The fifth step is to calculate an increase of color histogram bins with the linear weight and updating related color histograms if the color of the block is a pure color or calculating an increase of color histogram bins and brightness histogram bins with the linear weight and the linear weight and updating related color histograms and related brightness histograms if color of the block is a dark unsaturated color.
Preferably, the method describes at least two features of information by one composite histogram in a group of the feature information, wherein the feature information includes the color information and the brightness information of the image.